package com.leetcode.algorithm.y22.m09.w2;

import java.util.Arrays;

/**
 * 2389. 和有限的最长子序列
 * 
 * https://leetcode.cn/problems/longest-subsequence-with-limited-sum/
 * 
 * @author jie.deng
 *
 */
class Question2389Solution01 {

	public int[] answerQueries(int[] nums, int[] queries) {
		Arrays.sort(nums);
		int n = nums.length;
		int[] prefixSum = new int[n];
		prefixSum[0] = nums[0];
		for (int i = 1; i < n; i++) {
			prefixSum[i] = prefixSum[i - 1] + nums[i];
		}

		int m = queries.length;
		int[] ans = new int[m];
		for (int i = 0; i < ans.length; i++) {
			ans[i] = searchInsertIdx(prefixSum, queries[i]);
		}
		return ans;
	}

	private int searchInsertIdx(int[] arr, int target) {
		int left = 0;
		int right = arr.length;
		while (left < right) {
			int mid = left + ((right - left) >> 1);
			if (arr[mid] <= target) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		return left;
	}

}